//不使用任何内建的哈希表库设计一个哈希集合（HashSet）。 
//
// 实现 MyHashSet 类： 
//
// 
// void add(key) 向哈希集合中插入值 key 。 
// bool contains(key) 返回哈希集合中是否存在这个值 key 。 
// void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。 
// 
//
// 示例： 
//
// 
//输入：
//["MyHashSet", "add", "add", "contains", "contains", "add", "contains", 
//"remove", "contains"]
//[[], [1], [2], [1], [3], [2], [2], [2], [2]]
//输出：
//[null, null, null, true, false, null, true, null, false]
//
//解释：
//MyHashSet myHashSet = new MyHashSet();
//myHashSet.add(1);      // set = [1]
//myHashSet.add(2);      // set = [1, 2]
//myHashSet.contains(1); // 返回 True
//myHashSet.contains(3); // 返回 False ，（未找到）
//myHashSet.add(2);      // set = [1, 2]
//myHashSet.contains(2); // 返回 True
//myHashSet.remove(2);   // set = [1]
//myHashSet.contains(2); // 返回 False ，（已移除） 
//
// 
//
// 提示： 
//
// 
// 0 <= key <= 10⁶ 
// 最多调用 10⁴ 次 add、remove 和 contains 
// 
//
// Related Topics 设计 数组 哈希表 链表 哈希函数 👍 341 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-04-14 14:16:58
 * @description 705.设计哈希集合
 */
public class DesignHashset{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 DesignHashset fun=new DesignHashset();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
//class MyHashSet {
//         private static final int mod =769;
//         private LinkedList<Integer> [] data;
//
//    public MyHashSet() {
//        data=new LinkedList[mod];
//        for (int i = 0; i < mod; i++) {
//            data[i]=new LinkedList<Integer>();
//        }
//    }
//
//    public void add(int key) {
//        int h=hash(key);
//        Iterator<Integer> iterator = data[h].iterator();
//        while (iterator.hasNext()){
//            Integer next = iterator.next();
//            if(next==key){
//                return;
//            }
//        }
//        data[h].offerLast(key);
//    }
//
//    public void remove(int key) {
//        int h=hash(key);
//        Iterator<Integer> iterator = data[h].iterator();
//        while (iterator.hasNext()){
//            Integer next = iterator.next();
//            if(next==key){
//                data[h].remove(next);
//                return;
//            }
//        }
//
//    }
//
//    public boolean contains(int key) {
//        int h=hash(key);
//        Iterator<Integer> iterator = data[h].iterator();
//        while (iterator.hasNext()){
//            Integer next = iterator.next();
//            if(next==key){
//                return true;
//            }
//        }
//        return false;
//    }
//    public int hash(int key){
//        return key%mod;
//    }
//}
//桶的思想，数据不超过10^6，int32位，所以数组不超过40000
	//key/32得到在哪个桶，余数得到具体位置
	class MyHashSet {
		int[] bs = new int[40000];
		public void add(int key) {
			int bucketIdx = key / 32;
			int bitIdx = key % 32;
			setVal(bucketIdx, bitIdx, true);
		}

		public void remove(int key) {
			int bucketIdx = key / 32;
			int bitIdx = key % 32;
			setVal(bucketIdx, bitIdx, false);
		}

		public boolean contains(int key) {
			int bucketIdx = key / 32;
			int bitIdx = key % 32;
			return getVal(bucketIdx, bitIdx);
		}

		void setVal(int bucket, int loc, boolean val) {
			//为true，这个位置设置为1，直接或
			if (val) {
				int u = bs[bucket] | (1 << loc);
				bs[bucket] = u;
			} else {
				//为false，这个位置设置为0，先对1<<loc取反，然后与，其余位置不变，当前位置变成0
				int u = bs[bucket] & ~(1 << loc);
				bs[bucket] = u;
			}
		}

		boolean getVal(int bucket, int loc) {
			int u = (bs[bucket] >> loc) & 1;
			return u == 1;
		}
	}


/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
